package binary

import (
	"log"
	"math"
	"runtime"
	"sort"
)

// 检查最小距离minLen 是否满足
func check(position []int, ballNum int, minLen int) bool {
	// 起始位置肯定要放球
	ballNum--
	currentPos := 1
	lastPos := 0
	for ballNum > 0 && currentPos < len(position) {
		if position[currentPos]-position[lastPos] >= minLen {
			lastPos = currentPos
			ballNum--
		}
		currentPos++
	}
	if 0 == ballNum {
		return true
	} else {
		return false
	}
}

// https://leetcode-cn.com/problems/magnetic-force-between-two-balls/
func MaxDistance(position []int, m int) int {
	pc, _, _, _ := runtime.Caller(1)
	log.Println(runtime.FuncForPC(pc).Name())
	pcArr := make([]uintptr, 20)
	pcCount := runtime.Callers(0, pcArr)
	for i := 0; i < pcCount; i++ {
		f := runtime.FuncForPC(pcArr[i])
		fileName, lineName := f.FileLine(pcArr[i])
		log.Printf("%s:%s %s", fileName, lineName, f.Name())
	}
	sort.Ints(position)

	// 开始二分搜索
	retDis := 0
	maxDis := (position[len(position)-1] - position[0]) / (m - 1)
	minDis := math.MaxInt32
	for index := 0; index < len(position)-1; index++ {
		currentDis := position[index+1] - position[index]
		if minDis > currentDis {
			minDis = currentDis
		}
	}

	leftDis, rightDis := minDis, maxDis
	for leftDis <= rightDis {
		midDis := (leftDis + rightDis) / 2
		if check(position, m, midDis) {
			leftDis = midDis + 1
			retDis = midDis
		} else {
			rightDis = midDis - 1
		}
	}
	return retDis
}
